Network congestion generally refers to overloading the resources of a network, such as routers and switches, with packets that need to be handled. When network congestion occurs, packets are dropped by an overloaded resource and have to be retransmitted. Numerous methods and proposals for avoiding network congestion are known, but each has its own drawbacks with respect to issues such as fairness, (e.g., which packets get dropped), enforcement, practical implementation difficulties, and so forth.
For example, in the Transmission Control Protocol (TCP), network congestion is controlled via various phases and techniques, including a congestion avoidance phase. TCP controls its transmit rate by a congestion window that determines the maximum amount of data that may be in transit at any time, wherein a congestion window's worth of data is transmitted every round-trip time. In the absence of congestion, TCP increases its congestion window by one packet each round-trip time. To avoid congestion, if the network drops any packet, TCP halves its congestion window. However, detecting congestion through packet loss, typically as a result of overflow in a router's output queue, has a number of drawbacks including that this method is reactive rather than proactive, as by the time the (often substantial) router buffers are filled up and packets start to get dropped, the network is seriously overloaded. Consequently, the “normal” operating state of the network is to have substantial queuing delays in each router. Moreover, only those flows whose packets are dropped are aware of the congestion, which is why TCP needs to back off aggressively and halve the congestion window. The dropped packets often are not from the source that initially caused the congestion.
A more proactive attempt to avoid network congestion based on the above reduce-on-dropped-packets scheme is “Random Early Detection” (RED). RED operates by randomly discarding more and more packets as the network gets more and more congested, whereby the various sources' TCP congestion avoidance mechanisms halve their congestion windows before full congestion occurs. Packets are discarded with a probability computed from many parameters and variables, including the smoothed length of the forwarding queue. This scheme also has its drawbacks, as among other things, packets are unnecessarily dropped before the network is actually full.
A proposed improvement to TCP/IP, known as Explicit Congestion Notification (ECN), would mark the packets (e.g., that would be dropped in RED) instead of actually dropping them. The mark is returned to the source, whereby the source may slow down its rate of transmission. More particularly, ECN would work to signal the onset of congestion by setting a single bit in the IP packet header. To aid incremental deployment in the Internet, ECN aware traffic flows would identify themselves by setting a further bit in the IP header, whereby non-aware flows could have their packets discarded as normal. When received, the destination (TCP sink) sends back these ECN bits to the source (e.g., in an acknowledgement packet, or ACK) as a TCP option, whereby the source reacts to the ECN signals in the same way as TCP reacts to lost packets, for instance, by halving the congestion window on receipt of such a signal.
As an alternative to the above models, theorists have suggested congestion pricing as a possible solution to network congestion problems. In essence, these congestion pricing theories suggest that each router in the network should charge all sources responsible for network congestion, (e.g., by an in-band marking of their packets). Then, in the acknowledgement from the destination or by some other means, each source is notified of the total congestion caused, such that sources will voluntarily reduce their transmit rates based on their “willingness to pay.”
Various such network congestion pricing schemes have been designed and/or implemented. For example, U.S. patent application Ser. No. 10/010,881, filed Nov. 8, 2001, assigned to the assignee of the present invention and hereby incorporated by reference herein in its entirety, is directed to controlling network demand via congestion pricing, and describes a number of practical designs and/or implementations having many beneficial properties.
Such schemes for controlling (or indicating) levels of congestion typically require the measuring of the network load on the link or links in the network. Generally, measuring the load is accomplished by monitoring the packets being sent on the link relative to the capacity of the link.
However, this can be particularly problematic when the capacity of the link is variable rather than fixed, which may occur for a variety of reasons and in a variety of circumstances, both actual and effective. For example, compression can vary the effective capacity of a link, as the amount of compression achieved varies with the type of data being compressed. Another example is when additional physical links or transmission channels are added or removed depending on network usage, e.g., in a system that dials-up additional links as needed. Yet another example is wireless technology. Wireless technology is unable to detect transmitted packet collisions, and thus uses a collision avoidance protocol to lower the probability of packets colliding. Among other characteristics of this protocol, packet transmissions are spread out, with long intervals provided between packets. One result of long intervals between packets is that the amount of capacity used to send a packet is more than simply the size of the packet. Moreover, since packet sizes vary and the intervals are not dependent on packet size, there is no simple ratio between packet size and the amount of capacity consumed, and thus packet sizes influence the effective capacity.
Further, a wireless protocol dynamically adjusts the transmission rate based on the current signal quality, which is measured, and thus the capacity varies based on current radio frequency (RF) noise. More particularly, when significant RF noise is present, the length of time that each bit is transmitted is increased (e.g., doubled) to facilitate reception, which slows the rate. Conversely, the bit transmission length may be decreased as signal quality improves, which increases the rate up to some maximum.
In summary, at least some (e.g., price-based) schemes avoid or reduce network congestion operate by controlling (e.g., throttling back) output transmissions based on a current amount of congestion, which depends on the current capacity of the transmission link. However, when the capacity is variable, an accurate measure of the current capacity and network load is needed for such schemes to properly operate.